蟻本 2-4 食物連鎖
code: python
N = int(input())
K = int(input())
T = list(map(int, input().split()))
X = list(map(int, input().split()))
Y = list(map(int, input().split()))
class UnionFind:
def __init__(self, n):
# 親要素のノード番号を格納。parx == xの時そのノードは根(最初は全て根)
self.par = i for i in range(n)
# 木の高さを格納する（初期状態では0）
self.rank = 0 * n
# 検索
def find(self, x):
# 根ならその番号を返す
if self.parx == x:
return x
# 根でないなら、親の要素で再検索
else:
# 走査していく過程で親を書き換える(return xが代入される)
self.parx = self.find(self.parx)
return self.parx
# 併合
def union(self, x, y):
# 根を探す
x = self.find(x)
y = self.find(y)
if x == y:
return
# 木の高さを比較し、低いほうから高いほうに辺を張る
if self.rankx < self.ranky:
self.parx = y
else:
self.pary = x
# 木の高さが同じなら片方を1増やす
if self.rankx == self.ranky:
self.rankx += 1
# 同じ集合に属するか判定
def same(self, x, y):
return self.find(x) == self.find(y)
# x, x + n, x + 2 * n を x-A, x-B, x-Cの要素とする
UF = UnionFind(N * 3)
ans = 0
for i in range(K):
t = Ti
x, y = Xi - 1, Yi - 1 # 0, ..., N -1 の範囲にする
# 正しくない番号
if (x < 0 or N <= x or y < 0 or N <= y):
ans += 1
continue
if (t == 1):
# 「xとyは同じ種類」という情報
# もし違う範囲にいれば
if (UF.same(x, y + N) or UF.same(x, y + 2 * N)):
ans += 1
else:
UF.union(x, y)
UF.union(x + N, y + N)
UF.union(x + N * 2, y + N * 2)
else:
# 「xはyを食べる」という情報
# AはAを食べないし、AはCを食べない
if (UF.same(x, y) or UF.same(x, y + 2 * N)):
ans += 1
else:
UF.union(x, y + N)
UF.union(x + N, y + 2 * N)
UF.union(x + 2 * N, y)
print(ans)
# 100
# 7
# 1 2 2 2 1 2 1
# 101 1 2 3 1 3 5
# 1 2 3 3 3 1 5
テーマ
#UnionFind